package com.kitty.record.kittyalgorithm.basicalgorithm;

import com.sun.org.apache.xpath.internal.WhitespaceStrippingElementMatcher;

import javax.security.auth.login.AccountExpiredException;
import java.util.Arrays;

/**
 * @Description 快速排序
 *
 * 快速排序的原理：选择一个关键值作为基准值。
 * 比基准值小的都在左边序列（一般是无序的），
 * 比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
 * 详见：https://blog.csdn.net/shujuelin/article/details/82423852
 * @Author SHEN
 * @Date 2020/12/31
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] arr = new int[]{4,6,5,8,2,3,9,3};

        fastSort(arr);

        System.out.println("arr = " + Arrays.toString(arr));


    }







    public static void fastSort(int[] array){

        //superSort(array,0,array.length-1);

        generalSort(array,0,array.length-1);
    }


    //快速排序正常版本（便于理解）
    private static void generalSort(int[] a, int low, int high) {

        if(low > high){
            return;
        }

        int start = low;

        int end = high;

        int key = a[low];

        while(end > start){
            //从后往前查找找到一个比key小的数
            while(end > start && a[end] >= key){
                end--;
            }

            while (end > start && a[start] <= key){
                start++;
            }

            if(start < end){
                //交换
                int tmp;
                tmp = a[start];
                a[start] = a[end];
                a[end] = tmp;
            }
        }

        //最后将基准位与start和end相等的地方交换
        a[low] = a[start];
        a[start] = key;

            //递归调用左半数组
            generalSort(a, low, start-1);

            //递归调用右半数组
            generalSort(a, end+1, high);
    }



    //快速排序优化版本
    public static void superSort(int[] a, int low,int high){

        int start = low;

        int end = high;

        int key = a[low];

        while (end > start){

            //从后往前查找找到一个比key小的数
            while (end > start && a[end] >= key){
                end--;
            }

            if(a[end] <= key){
                //交换
                int tmp = a[end];
                a[end] = a[start];
                a[start] = tmp;
            }

            //从前往后查找找到一个比key大的数
            while (end > start && a[start] <= key){
                start++;
            }

            if(a[start] >= key){
                //交换
                int tmp = a[start];
                a[start] = a[end];
                a[end] = tmp;
            }

            if(start > low){
                superSort(a,low,start-1);
            }

            if(end < high){
                superSort(a,end+1,high);
            }
        }

    }

}
